#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char f){
  char ch=getchar();
  int sgn=1;
  int v=0;
  if(ch=='-')sgn=-1;
  else{
    assert('0'<=ch && ch<='9');
    v=ch-'0';
  }
  while(true){
    char ch=getchar();
    if(ch==f)break;
    assert('0'<=ch && ch<='9');
    v=v*10+ch-'0';
  }
  return v*sgn;
}
const int mx=1e5+10;
int a[mx];
const int mxl=20;
vector<int>g[mx];
vector<uli>w[mx];
int rmq[mxl][mx+mx];
int fst[mx],lst[mx];
int lyr[mx];
uli dep[mx];
bool hidden[mx];
vector<int>eul;
void dfs(int u,int pu){
  eul.push_back(u);
  for(int i=0;i<int(g[u].size());i++){
    int v=g[u][i];
    uli c=w[u][i];
    if(v!=pu){
      lyr[v]=1+lyr[u];
      dep[v]=dep[u]+c;
      dfs(v,u);
      eul.push_back(u);
    }
  }
}
int minimo(int l,int r){
  int len=32-__builtin_clz(r-l+1)-1;
  int x=rmq[len][l];
  int y=rmq[len][r-(1<<len)+1];
  if(lyr[x]<lyr[y])return x;
  return y;
}
int lca(int u,int v){
  if(lst[u]>lst[v])swap(u,v);
  int from=lst[u];
  int to=fst[v];
  if(from>to)to=lst[v];
  return minimo(from,to);
}

struct diameter{
  int t[2];
  uli l;
  bool operator <(diameter d)const{
    return l<d.l;
  }
};
diameter join(diameter a,diameter b){
  diameter ans=max(a,b);
  for(int i=0;i<2;i++)for(int j=0;j<2;j++){
    int u=a.t[i];
    int v=b.t[j];
    int z=lca(u,v);
    uli len=dep[u]+dep[v]-dep[z]-dep[z];
    ans=max(ans,{u,v,len});
  }
  return ans;
}
int p[mx];
diameter diam[mx];
int gp(int u){ return (u==p[u]?u:p[u]=gp(p[u])); }
const int mxa=1e4+10;
vector<int>divs[mxa];
vector<pair<int,int> >nodes[mxa];
int main(){
  for(int i=1;i<mxa;i++)
    for(int j=i;j<mxa;j+=i)
      divs[j].push_back(i);
  int t=rint('\n');
  assert(1<=t && t<=100);
  while(t--){
    int n=rint('\n');
    assert(2<=n && n<=1e5);
    for(int i=0;i<n;i++){
      a[i]=rint((i==n-1)?'\n':' ');
      assert(1<=a[i]&&a[i]<=1e4);
      g[i].clear();
      w[i].clear();
      for(int d:divs[a[i]])nodes[d].clear();
      fst[i]=lst[i]=-1;
    }
    for(int i=0;i<n;i++)for(int d:divs[a[i]])nodes[d].push_back({a[i],i});
    for(int i=0;i<n-1;i++){
      int u=rint(' ');
      int v=rint(' ');
      int c=rint('\n');
      assert(1<=u && u<=n);
      assert(1<=v && v<=n);
      assert(1<=c && c<=1e5);
      g[--u].push_back(--v);
      g[v].push_back(u);
      w[u].push_back(c);
      w[v].push_back(c);
    }
    eul.clear();    
    dfs(0,0);
    int es=eul.size();
    for(int i=0;i<es;i++){
      int ei=eul[i];
      rmq[0][i]=ei;
      if(fst[ei]==-1)fst[ei]=i;
      lst[ei]=i;
    }
    for(int l=1;l<mxl;l++){
      for(int i=0;i<es;i++){
        rmq[l][i]=rmq[l-1][i];
        int j=i+(1<<(l-1));
        if(j<es && lyr[rmq[l-1][j]]<lyr[rmq[l][i]])
          rmq[l][i]=rmq[l-1][j];
      }
    }   
    uli ans=0;
    for(int g=1;g<mxa;g++)if(!nodes[g].empty()){
      sort(nodes[g].begin(),nodes[g].end(),greater<pair<int,int> >());
      for(auto au:nodes[g]){
        int u=au.second;
        p[u]=u;
        diam[u]={{u,u},0};
        hidden[u]=true;
      }
      for(auto au:nodes[g]){
        uli mini=au.first;
        int u=au.second;
        for(int v: ::g[u])if(a[v]%g==0 && !hidden[v]){
          int pu=gp(u);
          int pv=gp(v);
          if(pu==pv)continue;
          auto d=join(diam[pu],diam[pv]);
          p[pv]=pu;
          diam[pu]=d;
          uli bet=d.l*mini*g;
          ans=max(ans,bet);
        }
        hidden[u]=false;
      }
    }
    printf("%lld\n",ans);
  }
  assert(getchar()==EOF);
  return 0;
}